package leetcode_101_120;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class levelOrderBottom_107 {
    /**
     *按从叶子节点所在层到根节点所在的层，逐层从左向右遍历
     * @param root 二叉树的根节点
     * @return 其节点值 自底向上的层序遍历
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
/**
 * 还是挺简单的，标记好每一层是第几层。对应好是第几个集合即可
 * 最后反序输出即可
 */
        List<List<Integer>>ans=new ArrayList<>();
        dfs(root,1,ans);
        Collections.reverse(ans);
        return ans;
    }
    void dfs(TreeNode node,int k,List<List<Integer>>ans) {
        if(node==null)
            return;
        if(k>ans.size()){  //说明此时的第k层的集合不存在
            List<Integer>list=new ArrayList<>();
            list.add(node.val);
            ans.add(list);
        }else {//存在第k层的集合，直接添加元素
            ans.get(k-1).add(node.val);
        }
        dfs(node.left,k+1,ans);
        dfs(node.right,k+1,ans);
    }
}
